package dynamic;

public class LongestBitonicSubsequence
{
  /*
   * lbs() returns the length of the Longest Bitonic Subsequence in
   * arr[] of size n. The function mainly creates two temporary arrays
   * lis[] and lds[] and returns the maximum lis[i] + lds[i] - 1.
   * lis[i] ==> Longest Increasing subsequence ending with arr[i]
   * lds[i] ==> Longest decreasing subsequence starting with arr[i]
   */
  int lbs(int arr[], int n)
  {
    int i, j;

    /*
     * Allocate memory for LIS[] and initialize LIS values as 1 for
     * all indexes
     */
    int[] lis = new int[n];
    for (i = 0 ; i < n ; i++)
      lis[i] = 1;

    /* Compute LIS values from left to right */
    for (i = 1 ; i < n ; i++)
      for (j = 0 ; j < i ; j++)
        if (arr[i] > arr[j] && lis[i] < lis[j] + 1) lis[i] = lis[j] + 1;

    /*
     * Allocate memory for lds and initialize LDS values for
     * all indexes
     */
    int[] lds = new int[n];
    for (i = 0 ; i < n ; i++)
      lds[i] = 1;

    /* Compute LDS values from right to left */
    for (i = n - 2 ; i >= 0 ; i--)
      for (j = n - 1 ; j > i ; j--)
        if (arr[i] > arr[j] && lds[i] < lds[j] + 1) lds[i] = lds[j] + 1;

    /* Return the maximum value of lis[i] + lds[i] - 1 */
    int max = lis[0] + lds[0] - 1;
    for (i = 1 ; i < n ; i++)
      if (lis[i] + lds[i] - 1 > max) max = lis[i] + lds[i] - 1;
    return max;
  }

  /**
   * @param args
   */
  public static void main(String[] args)
  {
    // TODO Auto-generated method stub

  }

}
